package com.practice.dp;

import java.util.Arrays;


public class Jewelry {
	public long howMany(int[] values) {
		long count = 0;
		int N = values.length;
		int maxN = N*1000 + 1;
		int[][] C = combination(N+1);
		
		Arrays.sort(values);
		long[][] B = calc(values);
		reverse(values);
		long[][] F = calc(values);
		reverse(values);
		
		int i = 0;
		while (i < N) {
			int j = i;
			while (j < N && values[j]==values[i]) j++;
			
			int sameN = j - i;
			for (int k=0; k<sameN; k++) {
				int amount = (k+1) * values[i];
				for (int x=amount; x<maxN; x++) {
					count += B[i][x-amount] * F[N-i-k-1][x] * C[sameN][k+1];
				}
			}
			i = j;
		}
		
		return count;
	}
	
	private void reverse(int[] a) {
		int N = a.length;
		for (int i=0; i<N/2; i++) {
			int t = a[i];
			a[i] = a[N-i-1];
			a[N-i-1] = t;
		}
	}
	
	private long[][] calc(int[] values) {
		int N = values.length;
		int maxN = N*1000 + 1;
		long[][] T = new long[N+1][maxN];
		
		T[0][0] = 1;
		for (int i=0; i<N; i++) {
			for (int j=0; j<maxN; j++) {
				T[i+1][j] = T[i][j];
				if (j>=values[i]) T[i+1][j] += T[i][j-values[i]];
			}
		}
		
		return T;
	}
	
	private int[][] combination(int N) {
		int[][] C = new int[N][N];
		
		for (int i=0; i<N; i++) {
			C[i][0] = 1;
			C[i][i] = 1;
		}
		
		for (int i=1; i<N; i++) {
			for (int j=1; j<i; j++) {
				C[i][j] = C[i-1][j] + C[i-1][j-1];
			}
		}
		
		return C;
	}
}
